package com.fwpsl.graph.shortestpath.singlesource;

import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/4/15
 * @description: 单源最短路径抽象类
 */
public abstract class AbstractSingleSource<T> {

    protected static final int INF = Integer.MAX_VALUE;

    /**
     * 路径节点， 包含当前顶点、前驱顶点、以及最短路径
     * 支持：单条最短路径和多条最短路径
     */
    public class PathNode {

        /**
         * 单条最短路径
         */
        protected static final int PATH_NODE_TYPE_SINGLE = 1;
        /**
         * 多条最短路径
         */
        protected static final int PATH_NODE_TYPE_MULTI = 2;

        Vertex<T> currentVertex;
        Vertex<T> preVertex;
        Set<Vertex<T>> preVertexSet;
        int distance;

        /**
         * @param currentVertex
         * @param distance
         * @param type          1: 单条最短路径；2：多条最短路径
         */
        PathNode(Vertex<T> currentVertex, int distance, int type) {
            this.currentVertex = currentVertex;
            if (type == PATH_NODE_TYPE_SINGLE) {
                this.preVertex = null;
            } else {
                this.preVertexSet = null;
            }
            this.distance = distance;
        }
    }

    /**
     * 最短路径，仅一条
     *
     * @param graph
     * @param start
     * @return
     */
    public Map<Vertex<T>, PathNode> singlePathList(Graph<T> graph, Vertex<T> start) {
        return null;
    }

    /**
     * 最短路径，有多条
     *
     * @param graph
     * @param start
     * @return
     */
    public Map<Vertex<T>, PathNode> multiPathList(Graph<T> graph, Vertex<T> start) {
        return null;
    }

    /**
     * 打印最短路径（仅一条）
     *
     * @param distances
     * @param end
     */
    public void printSinglePath(Map<Vertex<T>, PathNode> distances, Vertex<T> start, Vertex<T> end) {
        PathNode endPath = distances.get(end);

        System.out.print("Distance from " + start.getData() + " to " + end.getData() + " is "
                + endPath.distance + "; path: ");
        Deque<Vertex<T>> deque = new LinkedList<>();
        deque.push(endPath.currentVertex);
        Vertex<T> preNode = endPath.preVertex;
        while (preNode != null) {
            deque.push(preNode);
            preNode = distances.get(preNode).preVertex;
        }

        StringJoiner sj = new StringJoiner(" -> ");
        while (!deque.isEmpty()) {
            sj.add(String.valueOf(deque.poll().getData()));
        }

        System.out.println(sj.toString());
    }

    /**
     * 打印最短路径（多条）
     *
     * @param distances
     * @param end
     */
    public void printMultiPath(Map<Vertex<T>, PathNode> distances, Vertex<T> start, Vertex<T> end) {
        PathNode endPath = distances.get(end);
        System.out.println("Distance from " + start.getData() + " to " + end.getData() + " is "
                + endPath.distance + "; path: ");

        int i = 1;
        List<Deque<T>> list = pathList(distances, endPath);
        for (Deque<T> de : list) {
            StringJoiner sj = new StringJoiner(" -> ");
            while (!de.isEmpty()) {
                sj.add(String.valueOf(de.poll()));
            }
            System.out.println("第" + i++ + "条路径：" + sj.toString());
        }

    }

    /**
     * 路径处理，todo 环路的过滤
     *
     * @param distances
     * @param pathNode
     * @return
     */
    private List<Deque<T>> pathList(Map<Vertex<T>, PathNode> distances, PathNode pathNode) {
        List<Deque<T>> list = new ArrayList<>();
        if (pathNode.preVertexSet == null || pathNode.preVertexSet.isEmpty()) {
            Deque<T> deque = new LinkedList<>();
            deque.offer(pathNode.currentVertex.getData());
            list.add(deque);

            return list;
        }

        for (Vertex<T> vertex : pathNode.preVertexSet) {
            List<Deque<T>> nodeList = pathList(distances, distances.get(vertex));
            for (Deque<T> deque : nodeList) {
                deque.offer(pathNode.currentVertex.getData());
            }
            list.addAll(nodeList);
        }

        return list;
    }

    /**
     * 测试单条最短路径方法
     */
    public void testSinglePathList(Graph<T> graph, T start, T end) {
        Vertex<T> startVextex = graph.getVertex(start);
        Vertex<T> endVertex = graph.getVertex(end);

        // 单条最短路径
        Map<Vertex<T>, PathNode> distances = singlePathList(graph, startVextex);
        if (distances != null) {
            printSinglePath(distances, startVextex, endVertex);
        }
    }

    /**
     * 测试多条最短路径方法
     */
    public void testMultiPathList(Graph<T> graph, T start, T end) {
        Vertex<T> startVextex = graph.getVertex(start);
        Vertex<T> endVertex = graph.getVertex(end);

        // 多条最短路径
        Map<Vertex<T>, PathNode> distances = multiPathList(graph, startVextex);
        if (distances != null) {
            printMultiPath(distances, startVextex, endVertex);
        }
    }
}
